package com.zy.algorithm.model;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;

/**
 * @author ZhaoYi
 * @date 2023/12/25 13:51
 * 完全二叉树是一种二叉树，其中除了最后一层外，其他层的节点都被填满，且所有节点都保持向左对齐。最后一层的节点靠左排列，如果最后一层不满，那么缺少的节点也必须出现在最左边。下面是一些完全二叉树的特点：
 * 节点编号：对于一个完全二叉树，可以按照从上到下、从左到右的顺序为每个节点编号。
 * 数量关系：假设完全二叉树的高度为h，那么它的节点总数在2^(h-1)到2^h-1之间。
 * 层序遍历：对于一个完全二叉树，最常用的遍历方式是层序遍历。层序遍历从根节点开始，按照从上到下、从左到右的顺序遍历节点。
 * 完全二叉树的特点使其在存储和遍历方面具有一些优势。由于其节点排列有序且紧密，因此既可以使用数组来存储，也可以使用链表来表示。同时，层序遍历的特点也使得在解决一些问题时更加方便。
 */
public class CompleteBinaryTree<T> {


    private List<T> data;


    public CompleteBinaryTree() {
        this.data = new ArrayList<>();
    }

    public void add(T t) {
        data.add(t);
    }

    public Integer getSize() {
        return data.size();
    }

    protected List<T> getData() {
        return data;
    }


    public Optional<NodeData<T>> getLeft(int index) {
        int i = 2 * index + 1;
        if (i < data.size()) {
            NodeData<T> tNodeData = new NodeData<>(data.get(i), i);
            return Optional.of(tNodeData);
        }
        return Optional.empty();
    }

    public Optional<NodeData<T>> getRight(int index) {
        int i = 2 * index + 2;
        if (i < data.size()) {
            NodeData<T> tNodeData = new NodeData<>(data.get(i), i);
            return Optional.of(tNodeData);
        }
        return Optional.empty();
    }

    public Optional<NodeData<T>> getParent(int index) {
        if (index == 0) {
            return Optional.empty();
        } else {
            int i = (index - 1) / 2;
            NodeData<T> tNodeData = new NodeData<>(data.get(i), i);
            return Optional.of(tNodeData);
        }
    }


}

